"""
解题思路

由于题目要求最多可执行 k 次字符替换操作，我们可以推断出最长的子字符串肯定包含出现次数最多的字符。
因此，我们只需要确保窗口中需要被替换的字符数不超过 k。使用滑动窗口可以有效地维护一个窗口，
并在遍历过程中动态地调整窗口的大小，从而找到满足条件的最长子字符串。滑动窗口算法的时间复杂度为 O(n)，
其中 n 是字符串的长度，因为它只需要遍历字符串一次。这是一种非常高效的算法。

在实现上我们通过k来判断窗口的大小，即小于k的时候移动end扩大窗口，大于k的时候收缩head来受小窗口
最后记录最大的窗口是多少即可。

"""
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        head, end = 0, 0
        counter = collections.Counter()
        res = 0
        while end < len(s):
            counter[s[end]] += 1
            # most_common 输入希望找到的前K和最大频次，返回一个数组，
            # 数组中的对象是二元组，分别是(key, vuale)
            # TODO 这一步存在大量的时间冗余，待优化
            max_char = counter.most_common(1)[0][1]
            if end - head + 1 - max_char > k:
                counter[s[head]] -= 1
                head += 1
            res = max(res, end - head + 1)
            end += 1
        return res
